#ifndef _BTREEINDEX_H
#define _BTREEINDEX_H

#include "Common.h"
#include <list>

static const int BTREEDEGREE = 32;

class Bitcask;
struct BtreeBucket;
class CacheItem;
class Item;
class PangDBCore;

class BtreeIndex
{
    friend class Bitcask;
    friend class PangDBCore;
public:
    enum SetMode
    {
        EXIST_NO_SET = 0,
        REPLACE,
        REPLACE_ONLY_EXIST,
    };

    BtreeIndex();
    ~BtreeIndex();
    void Init();
    void Destroy();

    //ret: item itself -- inserted (no replace)
    //     old item    -- replaced
    //     NULL        -- insert failed
    Item* Set(Item *item, int set_mode);

    //ret: A pointer -- got
    //     NULL      -- failed
    Item* Get(Item *item);

    //ret: Delete pointer -- deleted
    //     NULL -- not found
    Item* Delete(Item *item);
    u64 GetElementNum() {return element_num;}
    u64 GetMemUsed() {return mem_used;}

    int RebalanceOp;
    FuncCompare CompareFunc;

    BtreeBucket *leaf_head;
    BtreeBucket *leaf_tail;
private:

    struct Iterator
    {
        enum Direction
        {
            LEFT = 0, //Prev
            RIGHT = 1, //Next
        };

        void Prev(u32 steps = 1);
        void Next(u32 steps = 1);
        void SeekHead();
        void SeekTail();
        void Seek(char *key, u8 len);

        int direction;
        char key_str[256];
        u8 key_len;

        BtreeBucket *cur_bucket;
        int cur_bucket_pos;
    };

    void insert_node(BtreeBucket *node, Item *item, BtreeBucket *child, int *path);
    void delete_node(BtreeBucket *node, int pos, int count, int *path);
    void dfs_destroy(BtreeBucket *node);
    BtreeBucket* alloc_bucket();
    void free_bucket(BtreeBucket* bucket);


    int bucket_num;

    BtreeBucket *root;
    u64 element_num;
    u64 mem_used;

    //std::list<Cursor> cursors;
    RWLock rwlock;

};

#pragma pack(push)
#pragma pack(1)
struct BtreeBucket
{
    void MakeSpaceInBucket(int pos, int count);
    void DeleteInBucket(int pos, int count);
    void* MoveRightToNodeBucket(int count, BtreeBucket *right_neighbour, void *father_anchor);
    void* MoveLeftToNodeBucket(int count, BtreeBucket *left_neighbour, void *father_anchor);
    void MoveRightToLeafBucket(int count, BtreeBucket *right_neighbour);
    void MoveLeftToLeafBucket(int count, BtreeBucket *left_neighbour);
    void FixChildFatherLink();
    int FindPosNode(Item *item, int (*compare_func)(Item *, Item *));
    int FindPosLeaf(Item *item, int (*compare_func)(Item *, Item *));

    u8 layer;
    u8 element_num;
    void *ptrs[BTREEDEGREE*2+1];
    BtreeBucket *father;
    BtreeBucket *next_leaf;
    BtreeBucket *prev_leaf;
    SpinLock lock;
    u16 cursor_ref;
};
#pragma pack(pop)


int item_compare(Item *a, Item *b);


#endif
